#include "mySearch.h"
#include <iostream>
#include <string>


using namespace std;

SSTable::SSTable()
{
    length = 0;
    origin = nullptr;
}

SSTable::SSTable(int length,int* origin)
{
    this->length = length;
    this->origin = new int[length];
    for (int i = 0; i < length; i++) {
        this->origin[i] = origin[i];
    }
}

SSTable::~SSTable()
{

}

int SSTable::getLength()
{
    return this->length;
}

int* SSTable::getOrigin()
{
    return this->origin;
}

void SSTable::setLength(int length)
{
    this->length = length;
}

void SSTable::setOrigin(int* origin)
{
    this->origin = origin;
}

int SSTable::binSearch(int val)
{
    int left = 0;
    int right = length - 1;

    while (left <= right) {
        int mid = (left + right) / 2;

        if (origin[mid] == val) {
            return mid; // Element found at index mid
        }
        else if (origin[mid] < val) {
            left = mid + 1; // Search the right half
        }
        else {
            right = mid - 1; // Search the left half
        }
    }

    return -1; // Element not found
}

BSTreeNode::BSTreeNode()
{
    data = 0;
    lchild = nullptr;
    rchild = nullptr;
}

BSTreeNode::BSTreeNode(int data)
{
    this->data = data;
    this->lchild = this->rchild = nullptr;
}

BSTreeNode::BSTreeNode(int data, BSTreeNode* lchild, BSTreeNode* rchild)
{
    this->data = data;
    this->lchild = lchild;
    this->rchild = rchild;
}

BSTreeNode::~BSTreeNode()
{

}

int BSTreeNode::getData()
{
    return this->data;
}

BSTreeNode* BSTreeNode::getLChild()
{
    return this->lchild;
}

BSTreeNode* BSTreeNode::getRChild()
{
    return this->rchild;
}

void BSTreeNode::setData(int data)
{
    this->data = data;
}

void BSTreeNode::setLChild(BSTreeNode* lchild)
{
    this->lchild = lchild;
}

void BSTreeNode::setRChild(BSTreeNode* rchild)
{
    this->rchild = rchild;
}

BSTree::BSTree()
{
    num = 0;
    root = nullptr;
}

BSTree::BSTree(int num, int* data)
{
    this->num = num;
    root = nullptr;

    for (int i = 0; i < num; i++) {
        addNode(data[i]);
    }
}

BSTree::~BSTree()
{

}

int BSTree::getNum()
{
    return this->num;
}

BSTreeNode* BSTree::getRoot()
{
    return this->root;
}

void BSTree::setNum(int num)
{
    this->num = num;
}

void BSTree::setRoot(BSTreeNode* root)
{
    this->root = root;
}

void printTemp(BSTreeNode* root, string& result)
{
    if (root == nullptr) {
        return;
    }

    result += to_string(root->getData()) + " ";
    printTemp(root->getLChild(), result);
    printTemp(root->getRChild(), result);
}

string BSTree::printTree()
{
    string traversal;
    printTemp(root, traversal);
    return traversal;
}


bool BSTree::searchNode(int val){
    BSTreeNode* current = root;

    while (current != nullptr) {
        if (current->getData() == val) {
            return true; // Node found
        }
        else if (val < current->getData()) {
            current = current->getLChild(); // Search the left subtree
        }
        else {
            current = current->getRChild(); // Search the right subtree
        }
    }

    return false; // Node not found
}


bool BSTree::addNode(int val)
{
    BSTreeNode* newNode = new BSTreeNode(val);

    if (root == nullptr) {
        root = newNode;
        num++;
        return true; // Added to an empty tree
    }

    BSTreeNode* current = root;
    BSTreeNode* parent = nullptr;

    while (current != nullptr) {
        parent = current;

        if (val < current->getData()) {
            current = current->getLChild(); // Move to the left subtree
        }
        else if (val > current->getData()) {
            current = current->getRChild(); // Move to the right subtree
        }
        else {
            delete newNode; // Node with the same value already exists
            return false;
        }
    }

    if (val < parent->getData()) {
        parent->setLChild(newNode); // Attach as the left child
    }
    else {
        parent->setRChild(newNode); // Attach as the right child
    }

    num++;
    return true; // Node added successfully
}

bool BSTree::deleteNode(int val)
{
    BSTreeNode* current = root;
    BSTreeNode* parent = nullptr;
    bool isLeftChild = false;

    while (current != nullptr && current->getData() != val) {
        parent = current;

        if (val < current->getData()) {
            current = current->getLChild(); // Move to the left subtree
            isLeftChild = true;
        }
        else {
            current = current->getRChild(); // Move to the right subtree
            isLeftChild = false;
        }
    }

    if (current == nullptr) {
        return false; // Node to be deleted not found
    }

    // Case 1: Node to be deleted has no children
    if (current->getLChild() == nullptr && current->getRChild() == nullptr) {
        if (current == root) {
            root = nullptr; // Deleting the root node
        }
        else if (isLeftChild) {
            parent->setLChild(nullptr); // Deleting a left child
        }
        else {
            parent->setRChild(nullptr); // Deleting a right child
        }
    }
    // Case 2: Node to be deleted has one child
    else if (current->getRChild() == nullptr) {
        if (current == root) {
            root = current->getLChild(); // Deleting the root node with a left child
        }
        else if (isLeftChild) {
            parent->setLChild(current->getLChild()); // Deleting a left child with a left child
        }
        else {
            parent->setRChild(current->getLChild()); // Deleting a right child with a left child
        }
    }
    else if (current->getLChild() == nullptr) {
        if (current == root) {
            root = current->getRChild(); // Deleting the root node with a right child
        }
        else if (isLeftChild) {
            parent->setLChild(current->getRChild()); // Deleting a left child with a right child
        }
        else {
            parent->setRChild(current->getRChild()); // Deleting a right child with a right child
        }
    }
    // Case 3: Node to be deleted has two children
    else {
        BSTreeNode* successor = getSuccessor(current);

        if (current == root) {
            root = successor; // Deleting the root node with two children
        }
        else if (isLeftChild) {
            parent->setLChild(successor); // Deleting a left child with two children
        }
        else {
            parent->setRChild(successor); // Deleting a right child with two children
        }

        successor->setLChild(current->getLChild()); // Attach the left subtree of the node to be deleted
    }

    delete current;
    num--;
    return true; // Node deleted successfully
}

BSTreeNode* BSTree::getSuccessor(BSTreeNode* node) {
    BSTreeNode* current = node->getRChild();
    BSTreeNode* successorParent = nullptr;
    BSTreeNode* successor = node;

    while (current != nullptr) {
        successorParent = successor;
        successor = current;
        current = current->getLChild(); // Keep moving to the left subtree
    }

    if (successor != node->getRChild()) {
        successorParent->setLChild(successor->getRChild()); // Detach the successor from its parent
        successor->setRChild(node->getRChild()); // Attach the right subtree of the node to be deleted
    }

    return successor;
}
